% Exemplo de relatório técnico do IC

% Criado por P.J.de Rezende antes do Alvorecer da História.
% Modificado em 97-06-15 e 01-02-26 por J.Stolfi.
% modificado em 2003-06-07 21:12:18 por stolfi
% modificado em 2008-10-01 por cll
% \def\lastedit{2010-03-16 17:56:58 by stolfi}

\nonstopmode % PARA RODAR LATEX EM BATCH MODE
\documentclass[11pt,twoside]{article}

\usepackage{techrep-ic}

%%% SE USAR INGLÊS, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A SEGUIR:
\usepackage[brazil]{babel}
%% \usepackage[english]{babel}

%%% SE USAR CODIFICAÇÃO LATIN1 OU UTF-8, ATIVE UM DOS DOIS COMANDOS A
%%% SEGUIR:
%%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

%%% Para obter o tamanho de texto recomendado:
\usepackage[margin=1in]{geometry}

%%% Para simbolos de math
\usepackage{amsmath,amssymb,amsfonts,latexsym}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{color}

\definecolor{gray}{gray}{0.95}

\lstset{
  backgroundcolor=\color{gray},
  basicstyle=\ttfamily,
  breaklines=true,
  captionpos=b,
  columns=fixed,
  language=sh,
  showstringspaces=false,
  tabsize=2
}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Número do relatório
\TRNumber{01}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{13} % Dois dígitos
\TRMonth{03} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{R.A.Q. Cruz \and S.G. Fadel \and F.A. Neto}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{Análise de desempenho de algoritmos numéricos para o cálculo de $\pi$}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% O que segue é apenas uma sugestão - sinta-se à vontade para
% usar seu formato predileto, desde que as margens tenham pelo
% menos 25mm nos quatro lados, e o tamanho do fonte seja pelo menos
% 11pt. Certifique-se também de que o título e lista de autores
% estão reproduzidos na íntegra na página 1, a primeira depois da
% página de capa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{Cruz, Fadel e Neto}{Análise de desempenho de algoritmos numéricos para o cálculo de $\pi$}
\pagestyle{myheadings}
\thispagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TÍTULO e NOMES DOS AUTORES, completos, para a página 1.
% Use "\\" para quebrar linhas, "\and" para separar autores.
%
\title{Análise de desempenho de algoritmos numéricos para o cálculo de $\pi$}

\author{Rommel Anatoli Quintanilla Cruz \and Samuel Gomes Fadel \and Filipe
Alves Neto}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}

Desde o século I a.C., há registros da busca pelos matemáticos de métodos para
estimar o valor do número $\pi$. Este trabalho é parte da disciplina de
Programação Concorrente do ICMC/USP com o objetivo de desenvolver e analisar as
diferenças de três métodos de aproximação do $\pi$ sequencial e paralelamente.
Concluímos que os ganhos de desempenho com o paralelismo são perceptíveis, porém
limitados pelos métodos. A dependência entre as variáveis de iteração são o
principal fator dessa limitação. O único método que não possui limitações no
paralelismo, o Monte Carlo, não obteve boa aproximação mesmo com um grande
número de iterações.

\end{abstract}

\section{Introdução}

O número $\pi$ é a constante matemática que representa a razão entre a
circunferência do círculo e seu diâmetro. A história do cálculo de $\pi$ pode
ser dividida em três fases distintas. A primeira era começou por volta de 250
a.C. com o matemático grego Arquimedes de Siracusa através de métodos
experimentais. A segunda era começou no meio do século 17 depois da descoberta
da análise infinitesimal e expressões infinitas. Por volta de 1980, começou a
terceira e atual era do cálculo de $\pi$, quando os matemáticos descobriram como
utilizar conjuntamente multiplicação de números longos, algoritmos de alta
performance especificamente desenvolvidos para o cálculo de $\pi$ e a explosão
do crescimento da performance dos computadores~\cite{arndt:01}.

Este trabalho foi desenvolvido como parte do curso SC0143 - Programação
Concorrente do Instituto de Ciências Matemáticas e de Computação (ICMC) da
Universidade de São Paulo (USP).

Objetivamos calcular o valor de $\pi$ com precisão de 10 milhões de dígitos
corretos através dos métodos Borwein, Gauss-Legendre e Monte Carlo. Para cada
método serão desenvolvidos uma versão sequencial e uma paralela de modo a
analisar o speedup obtido \footnote{Os códigos dos programas desenvolvidos estão
hospedados no repositório do Google Code no endereço
https://code.google.com/p/pc2013-grupo06-turmab/.}.

\section{Métodos}

Os métodos utilizados no trabalho para estimar o valor de $\pi$ serão
apresentados em detalhes nesta seção.

\subsection{Borwein}
\label{sub:metodo-borwein}
Um método numérico iterativo para aproximar o valor de $\pi$, de convergência
quadrática, foi proposto por Jonathan M. Borwein e Peter B.
Borwein~\cite{borweinPi}. O método define, inicialmente, os valores:
\[
    x_0 = \sqrt{2} \text{,} \quad
    y_1 = \sqrt[4]{2} \quad \text{e} \quad
    \pi_0 = 2 + \sqrt{2}\text{.}
\]

Daí, a cada iteração $i$, $1 \leq i \leq n$,
\[
    x_i = \frac{1}{2}\left(x_{i-1}^{\frac{1}{2}} + x_{i-1}^{-\frac{1}{2}}\right)
    \text{,} \quad
    y_i = \frac{y_{i-1}x_{i-1}^{\frac{1}{2}} + x_{i-1}^{-\frac{1}{2}}}{y_{i-1} + 1}
    \quad \text{e} \quad
    \pi_i = \pi_{i-1}\frac{x_i + 1}{y_i + 1}\text{.}
\]

Como, para $n \geq 2$, $\pi_n$ descresce monotonicamente a $\pi$ com $\pi_n -
\pi < 10^{-2^{n+1}}$, $\pi_n$ conterá a melhor aproximação de $\pi$ após $n$
iterações.

\subsection{Gauss-Legendre}
\label{sub:metodo-gauss}

O método de Gauss-Legendre, também chamado de Salamin-Brent, é um método numérico
que aproxima o valor de $\pi$ em convergência quadrática. A fórmula original
deste método foi descoberta em 1973 e publicada em 1976 pelo matemático Eugene
Salamin~\cite{salamin:76}. Ao mesmo tempo e de forma independente, Richard
Brent~\cite{brent:76} chegou no mesmo resultado. Este método é baseado na média
aritmético-geométrica, estudada independentemente por Legendre e Gauss.

O algoritmo é dado pelos passos:
\begin{enumerate}
    \item Inicialize os valores:
          $
          a_0 = 1 \mbox{,   }
          b_0 = \frac1{\sqrt2} \mbox{,   }
          t_0 = \frac14 \mbox{,   }
          p_0 = 1 \mbox{.}
          $
    \item Repita até o número de iterações desejadas: \\
          $
          a_{n+1} = \frac{a_n + b_n}2 \mbox{,   }
          b_{n+1} = \sqrt{a_nb_n} \mbox{,   }
          t_{n+1} = t_n - p_n(a_n - a_{n+1})^2 \mbox{,   }
          p_{n+1} = 2p_n \mbox{.}
          $
    \item $\pi$ é aproximadamente:
          $ \pi \cong \frac{(a_n + b_n)^2}{4t_n} \mbox{.} $
\end{enumerate}


\subsection{Monte Carlo}

Em geral, chama-se Método de Monte Carlo qualquer método que resolve um problema
a partir da simulação baseada em uma série de números aleatórios. Estes algoritmos
têm natureza numérica e são úteis para o cálculo de expressões complexas ou de
problemas que não são fáceis de calcular analiticamente. Neste trabalho, vamos
falar sobre uma versão do método para o cálculo de uma aproximação de $\pi$.

Suponha que temos um círculo de raio 1 inscrito num quadrado, depois geramos
pontos aleatórios dentro deles, como a figura a seguir:

\begin{figure}[h]
   \centering
    \includegraphics[scale=0.25]{dardos.eps}
   \caption{Pontos aleatórios no quadrado de lado 2 centrado em $(0, 0)$}
   \label{montecarlo}
\end{figure}


Os pontos são gerados de tal maneira que a probabilidade de que um ponto caia
dentro do círculo seja:
\[
    \rho (\mbox{cai dentro do círculo}) = \frac{A_{circulo}}{A_{quadrado}} = \frac{\iint\limits_{x^2-y^2\leq 1} 1 \, \mathrm{d}x \, \mathrm{d}y }{ \iint\limits_{-1 \leq x,y \leq 1} 1 \, \mathrm{d}x \, \mathrm{d}y } = \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4}
\]

Rearranjado, temos:
\[
    \pi = 4 \times \rho (\mbox{cai dentro do círculo})
    \Rightarrow
    \pi \cong 4 \frac{n_c}{n} \text{.}
\]

Para calcular o valor de $\pi$ é preciso conhecer o valor da probabilidade de
que um ponto caia dentro do círculo, mas pode-se aproximar tal valor por meio da
razão entre o número de pontos dentro do círculo ($n_c$) e o número total de
pontos ($n$), desde que a distribuição dos pontos seja suficientemente uniforme.

Em comparação com outros métodos, o valor calculado se aproxima muito lentamente
a $\pi$, devido à convergência de ordem $\frac{1}{\sqrt n}$ do
erro~\cite{Johansen:07}, onde $n$ é a quantidade de pontos gerados. De fato,
como vamos verificar na fase experimental, cada novo dígito de precisão correto
custa cem vezes mais do que os dígitos corretos anteriores custaram.

\section{Implementação}

Nesta seção, serão apresentados os detalhes das implementações sequenciais e
paralelas de cada um dos métodos descritos na seção anterior.

Para compilar os programas, basta executar o comando \texttt{make} na pasta de
cada um dos métodos: \emph{browein}, \emph{gauss-legendre} e \emph{monte-carlo}.
A única dependência externa para compilação é a biblioteca GMP~\cite{gmp}. Para
executar a versão sequencial, utilize os comandos:
\begin{lstlisting}
./borwein-seq [NUM_ITER [PREC_BITS]]
./gauss-legendre-seq [NUM_ITER [PREC_BITS]]
./monte-carlo-seq [NUM_PONTOS]
\end{lstlisting}

Para a versão paralela:
\begin{lstlisting}
./borwein-par [NUM_ITER [PREC_BITS]]
./gauss-legendre-par [NUM_ITER [PREC_BITS]]
./monte-carlo-par [NUM_PONTOS]
\end{lstlisting}

Os parâmetros são:
\begin{itemize}
    \item \texttt{NUM\_ITER}: o número de iterações;
    \item \texttt{NUM\_PONTOS}: o número de pontos sorteados;
    \item \texttt{PREC\_BITS} a precisão de ponto flutuante em bits.
\end{itemize}

Caso omitidos, os valores padrão são 25 iterações, $10^7$ pontos sorteados e 35
milhões de bits de precisão.

\subsection{Borwein}
Para implementar o método Borwein, foram utilizadas a linguagem de programação C
e a biblioteca GMP.

Na versão sequencial do programa, primeiro inicializam-se as variáveis que
estarão envolvidas no cálculo de $\pi$. Depois, o programa executa a primeira
iteração separadamente das outras, pois o valor de $y_1$ já é definido no
início, então devemos calcular $x_1$, $\pi_0$ e $\pi_1$ antes de partir para o
laço principal. No laço, cada iteração é feita conforme definido pelo método e,
assim que o número dado de iterações for atingido, o laço termina e o programa
imprime na saída padrão o valor de $\pi_n$, onde $n$ é o número de iterações.

Em sua versão paralela, o programa foi dividido em três threads,
\texttt{thread\_x}, \texttt{thread\_y} e \texttt{thread\_p}, cada uma
responsável por calcular os valores de $x_i$, $y_i$ e $\pi_i$, respectivamente.
Os valores são calculados seguindo a própria definição do método.

Como existe dependência entre as variáveis, toda vez que uma thread vai acessar
alguma variável pela qual ela não é responsável por determinar o valor (como
quando \texttt{thread\_p} acessa $x_i$ e $y_i$), primeiro chama-se a função
\texttt{pthread\_mutex\_trylock} para verificar se o mutex relacionado a tal
variável está travado. Se estiver travado, também tenta-se travar o mutex, a fim
de que a thread interessada na variável se bloqueie até que a thread responsável
por tal variável a desbloqueie com a liberação do mutex. Assim, se um valor já
foi calculado pela thread responsável, não precisamos travar o mutex relacionado
e podemos usar livremente o valor calculado.

Para implementar a sincronização entre as threads, para cada iteração há um
mutex para cada variável ($x_i$, $y_i$ e $\pi_i$). Os mutexes seguem
nomenclatura:
\begin{itemize}
    \item \texttt{mut\_x[i]} para cada $x_i$;
    \item \texttt{mut\_sqrt\_x[i]} para cada $x_i^{\frac{1}{2}}$;
    \item \texttt{mut\_inv\_sqrt\_x[i]} para cada $x_i^{-\frac{1}{2}}$;
    \item \texttt{mut\_y[i]} para cada $y_i$.
\end{itemize}

No início do programa, após a inicialização das variáveis e dos mutexes, os
mutexes \texttt{mut\_x[0]} e \texttt{mut\_sqrt\_x[0]} são travados para que,
quando as threads começarem a calcular os valores das variáveis pelas quais são
responsáveis, esperem \texttt{thread\_x} calcular $x_0$ e $x_0^{1/2}$. Após
iniciar cada thread, o programa principal aguarda \texttt{thread\_p} terminar,
já que o valor calculado por ela, $\pi_n$, é o valor de $\pi$ que desejávamos
calcular. O programa então obtém o valor e o imprime na saída padrão.

Nos dois programas, o cálculo de $x_{i-1}^{1/2}$ e $x_{i-1}^{-1/2}$, necessário
para calcular as variáveis $x_i$ e $y_i$, é consideravelmente custoso
computacionalmente devido à alta precisão, então esses valores são armazenados
em variáveis temporárias a fim de melhorar desempenho do programa.

\subsection{Gauss-Legendre}

O método Gauss-Legendre foi implementado, neste trabalho, utilizando a linguagem
de programação C. A biblioteca GMP foi utilizada para obtermos a precisão
necessária do valor de $\pi$ e a versão paralela utiliza POSIX Pthreads.

Em sua versão sequencial, o programa implementado segue explicitamente o
algoritmo apresentado na subseção~\ref{sub:metodo-gauss}. Basicamente, o
programa inicializa os valores inicias, atualiza estes valores o número de
iterações desejadas e, com os valores finais, calcula o $\pi$ com a fórmula
dada.

A versão paralela por sua vez, além do algoritmo, contém alguns recursos extras.
Para cada um dos parâmetros para calcular o $\pi$ -- $a, b, t$ e $p$ --, foi
adicionado uma variável para armazenar em qual iteração está o parâmetro
associado e um mutex para evitar o acesso simultâneo à estas variáveis.
Portanto, esta versão contém quatro threads, cada uma responsável por calcular
os valores de um dos parâmetros e atualizar em que iteração estes estão. De modo
a evitar o acesso desnecessário às variáveis de iteração, cada thread mantém um
``buffer'' para saber em que iteração estão as demais threads.

Ambas as versões imprimem na saída padrão de erro (\texttt{stderr}) qual dos
parâmetros acabaram de ser calculados e em qual iteração estão. Na saída padrão
(\texttt{stdout}), os programas imprimem o valor final das casas decimais de
$\pi$ calculadas.

\subsection{Monte Carlo}

A implementação do Método de Monte Carlo foi feita em linguagem C através das seguintes
 etapas, nas quais para simplificar, o algoritmo trabalha apenas no primeiro quadrante,
sem alterar a proporção:
\begin{enumerate}
    \item Inicializar o contador de pontos dentro do círculo com 0
    \item Repetir $n$ vezes
    \begin{enumerate}
        \item Gerar aleatoriamente um ponto $(x, y) \in [0,1]\times[0,1]$
        \item Se o ponto $(x, y)$ está dentro do círculo adicionar 1 no contador
    \end{enumerate}
    \item Calcular a proporção $\frac{n_c}{n}$
    \item Multiplicar o valor do passo anterior por 4
\end{enumerate}

A versão paralela consiste em dividir a carga de trabalho total em partes iguais
para cada núcleo aproveitando a independência de cada cálculo.

Em ambas versões para gerar os números aleatórios se utilizou a biblioteca
padrão \texttt{stdlib}, no entanto para a versão sequencial se chamou à função
\texttt{rand()} e na versão paralela a \texttt{rand\_r()}. Essa distinção é
porque a versão paralela precisa de uma função geradora de números aleatórios
que seja segura em chamadas concorrentes e \texttt{rand\_r()} tem essa
propriedade chamada de \emph{reentrant}.

A fim de evitar o fenômeno chamado \emph{false sharing}, utilizou-se uma extensão
de C \texttt{\_\_attribute\_\_ ((aligned (64)))} sobre os tipos de dados que são
enviados como parâmetros para as threads.

\section{Resultados}
As tabelas a seguir mostram os resultados da execução de cada método, tanto da
versão sequencial como da versão paralela. Para cada método, foram executados
três testes para cinco número de iterações diferentes.

As linhas de cada tabela representam a média das medidas obtidas dos três
testes. Para os tempos de execução, é dado um intervalo de confiança de 95\%.
Na coluna \emph{Paralelismo}, o valor indicado corresponde ao uso total de CPU
pelo programa paralelo, sendo que este valor varia de 0\% a 400\%, dependendo do
número de núcleos (cores) ativos em sua execução e a utilização de cada um. O
speedup é calculado baseando-se na média dos tempos de execução da versão
sequencial divido pela média dos tempos de execução da versão paralela. Também
são dados para todos os testes o número de casas decimais corretas calculadas
para um certo número de iterações. No caso do método Monte Carlo, o número de
casas corretas pode variar para um mesmo número de iterações, devido a sua
natureza probabilística. A precisão dos pontos flutuantes nos métodos Borwein e
Gauss-Legendre, que utilizam a biblioteca GMP, foi de 35 milhões de bits.

Os testes foram realizados em um processador Intel Core i5 3570k operando à
frequência de 3.4GHz.
\begin{figure}
    \centering
    \begin{subfigure}{0.6\textwidth}
        \centering
        \includegraphics[width=\linewidth]{borwein_tempos.eps}
        \caption{Método Borwein}
        \label{fig:borwein-tempos}
    \end{subfigure}
    \begin{subfigure}{0.6\textwidth}
        \centering
        \includegraphics[width=\linewidth]{gauss-legendre_tempos.eps}
        \caption{Método Gauss-Legendre}
        \label{fig:gauss-legendre-tempos}
    \end{subfigure}
    \begin{subfigure}{0.6\textwidth}
        \centering
        \includegraphics[width=\linewidth]{monte-carlo_tempos.eps}
        \caption{Método Monte Carlo}
        \label{fig:monte-carlo-tempos}
    \end{subfigure}
    \caption{Tempos de execução}
    \label{fig:graficos}
\end{figure}



\begin{table}[h]
    \centering
    \label{tab:resultados_borwein}
    \begin{tabular}{ *{3}{r} *{2}{c} r }
    \hline
    Iterações   & T. Sequencial (s) & T. Paralelo (s)  & Paralelismo (\%) & Speedup & Decimais Corretas \\ \hline
    \hline
    5           & 21,815$\pm$0,078  & 14,191$\pm$0,005 & 152              & 1,537   & 82                \\ \hline
    10          & 40,124$\pm$0,055  & 23,192$\pm$0,008 & 176              & 1,730   & 2788              \\ \hline
    15          & 58,446$\pm$0,066  & 32,180$\pm$0,023 & 186              & 1,816   & 89408             \\ \hline
    20          & 76,797$\pm$0,064  & 41,201$\pm$0,012 & 192              & 1,864   & 2861294           \\ \hline
    25          & 98,070$\pm$0,196  & 51,190$\pm$0,036 & 198              & 1,916   & 10536048          \\ \hline
    \end{tabular}
    \caption{Resultados obtidos com o método Borwein.}
\end{table}

\begin{table}[h]
    \centering
    \label{tab:resultados_gausslegendre}
    \begin{tabular}{ *{3}{r} *{2}{c} r }
    \hline
    Iterações   & T. Sequencial (s) & T. Paralelo (s)  & Paralelismo (\%) & Speedup & Decimais Corretas \\ \hline
    \hline
    5           & 10,442$\pm$0,005  &  9,699$\pm$0,004 & 172              & 1,077   & 40                \\ \hline
    10          & 17,549$\pm$0,002  & 15,852$\pm$0,004 & 221              & 1,107   & 1391              \\ \hline
    15          & 24,740$\pm$0,020  & 21,985$\pm$0,014 & 243              & 1,125   & 44700             \\ \hline
    20          & 31,860$\pm$0,019  & 28,148$\pm$0,004 & 255              & 1,132   & 1430644           \\ \hline
    25          & 38,453$\pm$0,032  & 34,350$\pm$0,011 & 263              & 1,119   & 10536049          \\ \hline
    \end{tabular}
    \caption{Resultados obtidos com o método Gauss-Legendre.}
\end{table}

\begin{table}[h!]
    \centering
    \label{tab:resultados_montecarlo}
    \begin{tabular}{ *{3}{r} *{2}{c} r }
    \hline
    Iterações   & T. Sequencial (s)   & T. Paralelo (s)   & Paralelismo (\%) & Speedup & Decimais Corretas \\ \hline
    \hline
    $10^7$      &    0,214$\pm$0,009  &   0,050$\pm$0,001 & 384              & 4,245   & 4                 \\ \hline
    $10^8$      &    2,051$\pm$0,002  &   0,485$\pm$0,000 & 399              & 4,230   & 4                 \\ \hline
    $10^9$      &   20,382$\pm$0,009  &   4,847$\pm$0,001 & 399              & 4,205   & 4-5               \\ \hline
    $10^{10}$   &  204,170$\pm$0,034  &  48,462$\pm$0,002 & 399              & 4,213   & 4-5               \\ \hline
    $10^{11}$   & 2041,697$\pm$0,809  & 484,640$\pm$0,020 & 399              & 4,213   & 5-6               \\ \hline
    \end{tabular}
    \caption{Resultados obtidos com o método Monte Carlo.}
\end{table}

\section{Conclusões}

No método Borwein, pode-se ver que o speedup com o número de iterações. Isso
também se observa com mais do que 25 iterações. Por exemplo, com 50 iterações,
onde temos 223\% de uso de CPU e observa-se um speedup de 2,140. O número de
casas decimais corretas, conforme havia sido mostrado na seção
\ref{sub:metodo-borwein}, dobrou a cada iteração.

Em relação ao método Gauss-Legendre, apesar do paralelismo obtido ultrapassar
200\% para mais de 10 iterações, o speedup não ultrapassou 1.14 nos testes
realizados. Isto se deve à forte dependência das threads do programa. As casas
decimais corretas, conforme esperado pela natureza de convergência quadrática do
método, duplicaram a cada iteração, exceto para valores acima de 10 milhões de
casas decimais devido ao limite de precisão de ponto flutuante utilizado.

No método Monte Carlo, pode-se verificar que sua escalabilidade de processamento
paralelo só é limitada pelo número de núcleos, no entanto, não é alcançado um
crescimento notável na quantidade de decimais corretas. Nesse sentido, o tempo
geral de execução é diretamente proporcional ao número de pontos a se avaliar
tornando-se inviável o cálculo de mais de 7 decimais, por exemplo.

Comparado ao método Gauss-Legende, o método Borwein apresentou melhor
aproveitamento do paralelismo com o aumento do número de iterações, como pode
ser visto na figura \ref{fig:graficos}. Apesar de levar mais tempo para o mesmo
número de iterações, o método Borwein também acerta aproximadamente o dobro de
dígitos. O caso de acertar aproximadamente o mesmo número de dígitos com 25
iterações está ligado à limitação de 35 milhões de bits de precisão.
Considerando o método Monte Carlo, os métodos Borwein e Gauss-Legendre se
mostram muito superiores em tempo de execução e número de dígitos, porém não se
mostram tão escaláveis para paralelização quanto o método Monte Carlo.

\bibliographystyle{sbc}
\bibliography{relatorio1}

\end{document}
